/* 
 * Search in Rotated Sorted Array
 * duplicates are allowed
 * (1,2,1,1,1)
 */

#include "../../func.h"

bool search(vector<int> &nums, int targ)
{
    int first = 0, last = nums.size();
    while (first != last)
    {
        const int mid = first + (last - first) / 2;
        if (nums[mid] == targ)
            return true;
        if (nums[first] < nums[mid])
        {
            if (nums[first] < nums[mid])
            {
                if (nums[first] <= targ && targ < nums[mid])
                    last = mid;
                else
                    first = mid + 1;
            }
        }
        else if (nums[first] > nums[mid])
        {
            if (nums[mid] < targ && targ <= nums[last - 1])
                first = mid + 1;
            else
                last = mid;
        }
        else
        {
            first++;
        }
    }
    return false;
}